package tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 题目：二叉树的中序遍历结果(左根右)
 * @Author Gavin
 * @date 2022.01.02 09:16
 */
public class tree_8 {
    /**
     * 第一种方法：递归
     */
    //Time:O(n) Space:O(n)
    public static List<Integer> solution_1(TreeNode root){
        if(root==null)return new ArrayList<>();
        List<Integer> left=solution_1(root.left);//得到左子树的遍历集合
        left.add(root.val);//添加根节点
        List<Integer> right=solution_1(root.right);//得到右子树的遍历集合
        left.addAll(right);
        return left;
    }
    //下面这种方式可以遍历二叉树的任何方式。先序，中序，后序
    public static List<Integer> solution_3(TreeNode root){
        ArrayList<Integer> result = new ArrayList<>();
        if(root==null)return result;
        List<Integer> left=solution_3(root.left);
        List<Integer> right=solution_3(root.right);
        result.addAll(left);
        result.addAll(right);
        result.add(root.val);
        return result;
    }
    /**
     * 第二种方法：
     * 使用一个栈来处理，不断的将树的左节点入栈和出栈操作
     * 先将树的所有left节点入栈，
     * 然后依次出栈，然后右子树入栈
     */
    //Time:O(n) Space:O(n)
    public static List<Integer> solution_2(TreeNode root){
        List<Integer> result=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        while (root!=null||!stack.isEmpty()){
            while (root!=null){
                stack.push(root);
                root=root.left;
            }
            root=stack.pop();
            result.add(root.val);
            root=root.right;
        }
        return result;
    }

    public static void main(String[] args) {
        TreeNode left_1=new TreeNode(4,null,null);
        TreeNode right_1_=new TreeNode(5,null,null);
        TreeNode left=new TreeNode(2,left_1,right_1_);
        TreeNode right=new TreeNode(3,null,null);
        TreeNode root=new TreeNode(1,left,right);
        System.out.println(solution_2(root));
    }
}
